#include <stdio.h>
#include <fcntl.h>
#include <sys/types.h>
#include <sys/mman.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>

static int sma_initialized = 0; /* true if the sma has been initialized */
static int sma_numseg;          /* number of shm segments to allow */
static int sma_segsize;         /* size of each shm segment */
static int *sma_segments;       /* array of shm segment ids */
static void **sma_shmaddrs;     /* array of shm segment addresses */
static int sma_lastseg = 0;     /* index of MRU segment */
static int sma_lock;            /* sempahore to serialize access */

typedef struct header_t header_t;
struct header_t
{
    int segsize; /* size of entire segment */
    int avail;   /* bytes available (not necessarily contiguous) */
};

typedef struct block_t block_t;
struct block_t
{
    int size; /* size of this block */
    int next; /* offset in segment of next free block */
};
#define BLOCKAT(offset) ((block_t *)((char *)shmaddr + offset))
#define OFFSET(block) ((int)(((char *)block) - (char *)shmaddr))

#ifdef max
#undef max
#endif
#define max(a, b) ((a) > (b) ? (a) : (b))

enum
{
    POWER_OF_TWO_BLOCKSIZE = 0
}; /* force allocated blocks to 2^n? */

enum
{
    DEFAULT_NUMSEG = 1,
    DEFAULT_SEGSIZE = 30 * 1024 * 1024
};
void *apc_sma_malloc(size_t n);
void *create_mmap(int size)
{
    void *shmaddr;
    shmaddr = (void *)mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_SHARED | MAP_ANON, -1, 0);
    if (shmaddr == MAP_FAILED)
    {
        printf("创建内存空间出错");
        exit(0);
    }
    return shmaddr;
}

void memory_unmap(void *shmaddr, int size)
{
    munmap(shmaddr, size);
}

void *apc_emalloc(size_t n)
{
    void *p = (void *)malloc(n);
    if (p == NULL)
    {
        printf("apc_emalloc: malloc failed to allocate %u bytes:", n);
    }
    return p;
}
static int alignword(int x)
{
    typedef union
    {
        void *p;
        int i;
        long l;
        double d;
        void (*f)();
    } word_t;
    return sizeof(word_t) * (1 + ((x - 1) / sizeof(word_t)));
}

void apc_sma_init()
{
    int i;

    sma_numseg = 1;
    sma_segsize = DEFAULT_SEGSIZE;

    sma_segments = (int *)apc_emalloc(sma_numseg * sizeof(int));
    sma_shmaddrs = (void **)apc_emalloc(sma_numseg * sizeof(void *));

    for (i = 0; i < sma_numseg; i++)
    {
        header_t *header;
        block_t *block;
        void *shmaddr;
        sma_segments[i] = sma_segsize;
        sma_shmaddrs[i] = create_mmap(sma_segsize);
        shmaddr = sma_shmaddrs[i];

        header = (header_t *)shmaddr;
        header->segsize = sma_segsize;
        header->avail = sma_segsize - sizeof(header_t) - sizeof(block_t) -
                        alignword(sizeof(int));

        block = BLOCKAT(sizeof(header_t)); //空间首地址+header_t大小 是block的首地址
        block->size = 0;
        block->next = sizeof(header_t) + sizeof(block_t); //下一块的大小还是header_t
        //为了方便获取内存时的遍历 判断是否为0
        block = BLOCKAT(block->next);
        block->size = header->avail;
        block->next = 0;
    }
}

typedef struct slot_t slot_t;
struct slot_t
{
    char *key;            /* slot key */
    ulong value;          /* slot value */
    slot_t *next;         /* next slot in linked list */
    int num_hits;         /* number of hits to this bucket */
    time_t creation_time; /* time slot was initialized */
    time_t deletion_time; /* time slot was removed from cache */
};

typedef struct cache_header_t cache_header_t;
struct cache_header_t
{
    int num_hits;         /* total successful hits in cache */
    int num_misses;       /* total unsuccessful hits in cache */
    slot_t *deleted_list; /* linked list of to-be-deleted slots */
};

typedef struct apc_cache_t apc_cache_t; /* opaque cache type */
struct apc_cache_t
{
    void *shmaddr;          /* process (local) address of shared cache */
    cache_header_t *header; /* cache header (stored in SHM) */
    slot_t **slots;         /* array of cache slots (stored in SHM) */
    int num_slots;          /* number of slots in cache */
    int gc_ttl;             /* maximum time on GC list for a slot */
    int lock;               /* global semaphore lock */
};

//获取可用空间 每一个block块的大小是不一样的，这样在第一次初始化插槽数量的时候是最大的block块。每新建一个就会新增一个block块
//或者已有的block块还有剩余空间
static int sma_allocate(void *shmaddr, int size)
{
    header_t *header;    /* header of shared memory segment */
    block_t *prv;        /* block prior to working block */
    block_t *cur;        /* working block in list */
    block_t *prvbestfit; /* block before best fit */
    int realsize;        /* actual size of block needed, including header */
    int minsize;         /* for finding best fit */

    /* Realsize must be aligned to a word boundary on some architectures. */
    realsize = alignword(max(size + alignword(sizeof(int)), sizeof(block_t)));

    /*
     * Set realsize to the smallest power of 2 greater than or equal to
     * realsize. This increases the likelihood that neighboring blocks can be
     * coalesced, reducing memory fragmentation.
     */
    if (POWER_OF_TWO_BLOCKSIZE)
    {
        int p = 1;

        while (p < realsize)
        {
            p <<= 1;
        }
        realsize = p;
    }

    /*
     * First, insure that the segment contains at least realsize free bytes,
     * even if they are not contiguous.
     */
    header = (header_t *)shmaddr;
    printf("\n申请的空间：%d,可申请的空间：%d\n", realsize, header->avail);
    if (header->avail < realsize)
    {
        return -1;
    }

    prvbestfit = 0;    /* initially null (no fit) */
    minsize = INT_MAX; /* used to find best fit */

    prv = BLOCKAT(sizeof(header_t));
    while (prv->next != 0)
    {
        cur = BLOCKAT(prv->next);
        if (cur->size == realsize)
        {
            /* found a perfect fit, stop searching */
            prvbestfit = prv;
            break;
        }
        else if (cur->size > (sizeof(block_t) + realsize) &&
                 cur->size < minsize)
        {
            /* cur is acceptable and is the smallest so far */
            prvbestfit = prv;
            minsize = cur->size;
        }
        prv = cur;
    }
    if (prvbestfit == 0)
    {
        return -1;
    }

    prv = prvbestfit;
    cur = BLOCKAT(prv->next);

    /* update the block header */
    header->avail -= realsize;

    if (cur->size == realsize)
    {
        /* cur is a perfect fit for realsize; just unlink it */
        prv->next = cur->next;
    }
    else
    {
        block_t *nxt;  /* the new block (chopped part of cur) */
        int nxtoffset; /* offset of the block currently after cur */
        int oldsize;   /* size of cur before split */

        /* bestfit is too big; split it into two smaller blocks */
        nxtoffset = cur->next;
        oldsize = cur->size;
        prv->next += realsize;
        cur->size = realsize;
        nxt = BLOCKAT(prv->next);
        nxt->next = nxtoffset;
        nxt->size = oldsize - realsize;
    }

    return OFFSET(cur) + alignword(sizeof(int));
}

void *apc_sma_malloc(size_t n)
{
    int off;
    int i;

    off = sma_allocate(sma_shmaddrs[sma_lastseg], n);
    if (off != -1)
    {
        void *p = sma_shmaddrs[sma_lastseg] + off;
        return p;
    }

    for (i = 0; i < sma_numseg; i++)
    {
        if (i == sma_lastseg)
        {
            continue;
        }
        off = sma_allocate(sma_shmaddrs[i], n);
        if (off != -1)
        {
            void *p = sma_shmaddrs[i] + off;
            sma_lastseg = i;
            return p;
        }
    }
    return NULL;
}

apc_cache_t *apc_cache_create(int size_hint, int gc_ttl)
{
    apc_cache_t *cache;
    int cache_size;
    int num_slots;
    int i;
    num_slots = size_hint > 0 ? size_hint * 2 : 1000;

    cache = (apc_cache_t *)apc_emalloc(sizeof(apc_cache_t));
    cache_size = sizeof(cache_header_t) + num_slots * sizeof(slot_t *);

    cache->shmaddr = apc_sma_malloc(cache_size); //计算出可用空间，这里如果返回空 下一步设置空地址 也算一个bug

    memset(cache->shmaddr, 0, cache_size);

    cache->header = (cache_header_t *)cache->shmaddr; //新建一个header头 这个头不是空间的头了而是cache的头所以结构不一样
    cache->header->num_hits = 0;
    cache->header->num_misses = 0;
    cache->header->deleted_list = NULL;

    cache->slots = (slot_t **)(((char *)cache->shmaddr) + sizeof(cache_header_t)); //可用地址加上一个cache的头
    cache->num_slots = num_slots;
    cache->gc_ttl = gc_ttl;
    cache->lock = 0;

    for (i = 0; i < num_slots; i++)
    {
        cache->slots[i] = NULL; //设置每个slots的空间为空
    }

    return cache;
}
typedef struct apc_cache_key_t apc_cache_key_t;
struct apc_cache_key_t
{
    int device; /* the filesystem device */
    int inode;  /* the filesystem inode */
    int mtime;  /* the mtime of this cached file */
};
typedef struct apc_cache_entry_t apc_cache_entry_t;
struct apc_cache_entry_t
{
    char *filename; /* absolute path to source file */
    int ref_count;  /* concurrently executing processes */
};
static unsigned int hash(char *key)
{
    srand(time(0));
    return rand() % 2000 + 1;
    // return key.device + key.inode;
}
#define key_equals(a, b) (a.inode == b.inode && a.device == b.device)
slot_t *make_slot(char *key, ulong value, slot_t *next)
{
    slot_t *p = apc_sma_malloc(sizeof(slot_t));
    if (!p)
        return NULL;
    p->key = key;
    p->value = value;
    p->next = next;
    p->num_hits = 0;
    p->creation_time = time(0);
    p->deletion_time = 0;
    return p;
}

//插入数据
int apc_cache_insert(apc_cache_t *cache,
                     char *key,
                     ulong value)
{
    slot_t **slot;

    if (!value)
    {
        return 0;
    }

    // LOCK(cache);

    // /* 删除过期的 */
    // process_pending_removals(cache);

    slot = &cache->slots[hash(key) % cache->num_slots];
    // while (*slot)
    // {
    //     if (key_equals((*slot)->key, key))
    //     {
    //         if ((*slot)->key.mtime < key.mtime)
    //         {
    //             remove_slot(cache, slot);
    //             break;
    //         }
    //         UNLOCK(cache);
    //         return 0;
    //     }
    //     slot = &(*slot)->next;
    // }

    if ((*slot = make_slot(key, value, *slot)) == NULL)
    {
        return 0;
    }

    return 1;
}

typedef void *(*apc_malloc_t)(size_t);
void *apc_xmemcpy(const void *p, size_t n, apc_malloc_t f)
{
    void *q;

    if (p != NULL && (q = f(n)) != NULL)
    {
        memcpy(q, p, n);
        return q;
    }
    return NULL;
}

void *apc_xstrdup(const char *s, apc_malloc_t f)
{
    return s != NULL ? apc_xmemcpy(s, strlen(s) + 1, f) : NULL;
}

/* 
    本来是生成value的。这里改成生成key的。
    由于key原本是一个临时字符串。
    要把空间设置到申请的空间里 
*/
char *apc_cache_make_entry(const char *key)
{
    char *entry;
    entry = apc_xstrdup(key, apc_sma_malloc); //注意这里是直接传参的内存获取函数
    if (!entry)
        return NULL;
    return entry;
}

ulong apc_cache_find(apc_cache_t *cache, char *key)
{
    slot_t **slot;

    slot = &cache->slots[hash(key) % cache->num_slots];
    while (*slot)
    {
        if (strcmp((*slot)->key, key) == 0)
        {
            return (*slot)->value;
        }
        slot = &(*slot)->next;
    }
    return -1;
}
ulong mtime()
{
    struct timeval t;
    gettimeofday(&t, NULL);
    return ((ulong)t.tv_sec) * 1000 + (ulong)t.tv_usec / 1000;
}
int apc_module_init()
{
    printf("\n ---------------------------------------- \n");
    //初始化内存结构
    apc_sma_init();
    //初始化列表结构
    apc_cache_t *cache = apc_cache_create(1000, 3600);
    //插入KEY
    char *key1 = "aaaaa";
    char *key2 = "bbbbb";
    char *key3 = "ccccc";
    ulong value1 = mtime();
    usleep(300);
    ulong value2 = mtime();
    usleep(200);
    ulong value3 = mtime();
    apc_cache_insert(cache, apc_cache_make_entry(key1), value1);
    apc_cache_insert(cache, apc_cache_make_entry(key2), value2);
    apc_cache_insert(cache, apc_cache_make_entry(key3), value3);
    printf("\n首地址空间：%p\n", cache->shmaddr);
    printf("\ncache首地址空间：%p\n", cache);
    printf("\ncache_header_t：%X(Hex)\n", sizeof(cache_header_t));
    printf("\n插槽位置：%p\n", cache->slots);
    printf("\n插槽数量：%d\n", cache->num_slots);
    printf("\n查找Key1：%ld ,真值：%ld\n", apc_cache_find(cache, key1), value1);
    printf("\n查找Key2：%ld ,真值：%ld\n", apc_cache_find(cache, key2), value2);
    printf("\n查找Key3：%ld ,真值：%ld\n", apc_cache_find(cache, key3), value3);
    printf("\n ---------------------------------------- \n");
    return 0;
}

int main()
{

    apc_module_init();

    return 0;
}